package 力扣进阶面试题;

import 力扣题库.TreeNode;

public class p106从后序与中序遍历构造二叉树 {
    //因为是后序，所以在后序中找到 根节点后，先构建右树，再构建左树
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder==null || inorder==null) {
            return null;//只知道一个遍历结果无法构建二叉树
        }
        postindex=postorder.length-1;

        TreeNode root =buildTreeChild(postorder,inorder,0,inorder.length-1);
        return root;
    }

    public  int postindex=0;
    public TreeNode buildTreeChild(int[] postorder, int[] inorder,int inbegin,int inend) {
        if (inbegin>inend) {
            return null;//左树或右树为空
        }
        //二叉树的根
        TreeNode root=new TreeNode(postorder[postindex]);

        //在中序中 找二叉树的根
        int rootIndex=findRootIndex(inorder,inbegin,inend,postorder[postindex]);
        postindex--;

        //构建右子树
        root.right=buildTreeChild(postorder,inorder,rootIndex+1,inend);

        //构建右子树
        root.left=buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
        return root;
    }
    //找 当前根节点在中序中的下标
    public int findRootIndex(int[] inorder,int inbegin,int inend,int key) {
        for (int i = inbegin; i <=inend; i++) {
            if (inorder[i]==key) {
                return i;
            }
        }
        return -1;
    }
}
